#include <iostream>
#include <string.h>
using namespace std;
int count = 0;
void lcs(char *A, char* B, int** c, char** b);
void printLCS(char*A,char** b,int i,int j);
int main ()
{
    char* A = (char*)"ABCBDAB";
    char* B = (char*)"BDCABA";
    //cout << strlen(A)<<endl;
    int lengthA = strlen(A);
    int lengthB = strlen(B);

    int **c = new int*[lengthA+1];
    char **b = new char*[lengthA+1];
    for(int i=0; i< lengthA+1; ++i) {
        c[i] = new int[lengthB+1];
        b[i] = new char[lengthB+1];
    }
    lcs(A,B,c,b);
    cout<<"The result is:"<<c[lengthA][lengthB]<<endl;
    cout<<"The longest common subsequence is:"<<endl;
    printLCS(A,b,lengthA,lengthB);
    cout<<endl<<count<<endl;
    return 0;
}

void printLCS(char* A,char **b,int i,int j)
{
    ++count;
    if(0 == i || 0 ==j)return;
    if('\\' == b[i][j]) {
        printLCS(A,b,i-1,j-1);
        cout<<A[i-1];
    }
    else if('-' == b[i][j]) printLCS(A,b,i-1,j);
    else if('|' == b[i][j]) printLCS(A,b,i,j-1);
}

void lcs(char *A, char* B, int** c, char** b)
{
    int lengthA = strlen(A);
    int lengthB = strlen(B);
    
    for(int i=1; i<=lengthA; ++i) {
        c[i][0] = 0;
    }
    for(int j=1; j<=lengthB; ++j) {
        c[0][j] = 0;
    }
    for(int i=1; i<= lengthA; ++i) {
        for(int j=1; j<= lengthB; ++j) {
            if(A[i-1] == B[j-1]) {
                c[i][j] = c[i-1][j-1]+1;
                b[i][j] = '\\';
            }
            else {
                if(c[i-1][j] >= c[i][j-1]) {
                    c[i][j] = c[i-1][j];
                    b[i][j] = '-';
                }
                else {
                    c[i][j] = c[i][j-1];
                    b[i][j] = '|';
                }
            }
        }
    }
}


